#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// 377. 组合总和 Ⅳ
// https://leetcode.cn/problems/combination-sum-iv/description/

class Solution
{
public:
    int recursionTry(vector<int> &nums, int i, int target, vector<vector<int>> &dp)
    {
        if (i >= nums.size())
        {
            return 0;
        }
        if (target == 0)
        {
            return 1;
        }
        if (dp[i][target] != -1)
        {
            return dp[i][target];
        }
        int ans = 0;
        for (int i = 0; i < nums.size() && target >= nums[i]; i++)
        {
            ans += recursionTry(nums, i, target - nums[i], dp);
        }
        dp[i][target] = ans;
        return ans;
    }
    int combinationSum4(vector<int> &nums, int target)
    {
        vector<vector<int>> dp(nums.size(), vector<int>(target + 1, -1));
        sort(nums.begin(), nums.end());
        return recursionTry(nums, 0, target, dp);
    }
};

int main()
{
    return 0;
}